# KV V0.0.3 设计方案
[TOC]
## 背景
Key-value键值对存储在MCU项目中有很大的应用空间。BabyOS初期推出了一份比较粗糙的KV存储方案，现在希望对其进行重新设计，配合BabyOS使用，尽可能满足项目开发者的需要。
本次将记录详细的设计方案，有兴趣的爱好者均可以参与，讨论和修改方案，向BabyOS仓库提交代码。
问：开源社区已有easyflash等支持KV的项目了，怎么还重新搞一个呢？
答：出于两个方面：①技术爱好者不会停止“造轮子”，生命在于折腾。②希望BabyOS搭配的KV软件模块出自于BabyOS爱好者之手！
仓库地址：https://gitee.com/notrynohigh/BabyOS
文档地址：[https://gitee.com/notrynohigh/BabyOS/wikis/Key-Value模块V0.0.3设计方案](https://gitee.com/notrynohigh/BabyOS/wikis/BabyOS%20K-V%E8%AE%BE%E8%AE%A1%E6%96%B9%E6%A1%88)
[欢迎在wiki页面进行反馈和评论，也可以加入开发者群进行讨论！]
## 预期功能：
| 序号 | 功能点 | 一句话描述 | 备注 |
| ---- | ---------------- | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 1 | 读取 | 用户根据key值得到value | key: char * 字符串
value：
{
uint8_t *pvalue;
uint32_t len;
} |
| 2 | 查询value长度 | 用户根据key可以查询到对应value的长度 | |
| 3 | 修改（新建） | 用户根据key新建或修改值 | 新建和修改是一样的
只需要提供修改接口 |
| 4 | 删除 | 用户不需要一项key-value对，
通过key进行删除 | |
| 5 | 多区块 | 用户开辟了多块区域存储不同重要等级
的数据,多块区域都可以支持KV存储 | |
| 6 | 支持存储器 | 用户希望可以存数据的地方就可以使用KV | 使用BabyOS已有驱动
的存储器,持续更新 |
| 7 | 支持大数据块写入 | 用户希望写入的数据不局限于最小擦除单元 | |
| 8 | 支持擦写均衡 | 用户希望做到擦写均衡保证FLASH的寿命 | |
| 9 | 减小内存消耗 | 用户希望不要过多占用内存空间 | 实现后评估消耗内存的情况 |
## 旧方案的问题
①将key字符串转换为uint32_t类型的ID，无法避免有重复的ID出现。
原先这么设计主要是考虑比较数值快于比较字符串。待解决重复ID的问题。
②将存储空间分为两块，分为使用区和备份区。极大的降低了Flash的使用率。
③使用区域分为了表头区和数据区，无法以最优方案分配表头区和数据区各多少空间。
原先这么设计主要是考虑，表头区数据结构大小固定，可以快速查找。
④每次使用区域满后将数据整理到备份区，然后切换使用区和备份区的角色。数据搬运的频次多，而且量比较大。
重新设计存储策略，已保证预期功能的实现。
## V0.0.3设计方案
### 区块状态
区块：Flash的最小擦除大小。
区块存在以下几种状态：
Empty (空)、Writable（使用中）、Full（满）、Messy（待整理）、Joint（联合区块）
### 数据结构
考虑到有FLASH不支持单字节写入，数据结构每个单元使用4个字节宽度。
#### 区块头部结构
| 存储项 | 数据类型 | 说明 |
| ------ | ------------ | ---------------------------------------- |
| 标识符 | uint32_t | 固定 0x625F6B76 |
| 状态位 | uint32_t [3] | [0] 使用中
[1] 满/联合区块
[2]脏满 |
#### KV数据结构
| 存储项 | 数据类型 | 说明 |
| --------------- | -------- | ------------------------------------------------------------ |
| 标志符 | uint32_t | 固定 0x625F6B76 |
| 数据状态 | uint32_t | [31:24] 0xAA 已修改 0x55 已删除
[23:0] 修改后，存放的新地址
（新地址同区块可用，地址为当前区块的偏移地址
新地址跨区块则填0xFFFFFF） |
| key的md5值 | uint64_t | key计算md5的结果 |
| value的校验值 | uint32_t | value计算CRC32的结果 |
| key/value的长度 | uint32_t | [31:24] key的长度
[23] 联合体标记
[22:0] value的数据长度 |
| key | | key限制在 1~255个字符。 |
| value | | 数据由联合区块组成时，此处为联合区块地址
地址1/地址2.....每个地址占4个字节 |
### 区块整理
区块使用考虑均衡的问题，优先使用空区块，如果仅剩下1个空区块便进行脏区块的整理。
整理后的脏区块变为空区块，原先的空区块变为可写入区块。
| 区块1 | 2 | 3 | 4 |
| ------ | ------ | ------ | ------ |
| 空 | 空 | 空 | 空 |
| 脏满 | 空 | 空 | 空 |
| 脏满 | 脏满 | 空 | 空 |
| 脏满 | 脏满 | 脏满 | 空 |
| 空 | 脏满 | 脏满 | 可写入 |
| 空 | 脏满 | 脏满 | 脏满 |
| 可写入 | 空 | 脏满 | 脏满 |
| 脏满 | 空 | 脏满 | 脏满 |
| 脏满 | 可写入 | 空 | 脏满 |
| 脏满 | 脏满 | 空 | 脏满 |
| 脏满 | 脏满 | 可写入 | 空 |
| 脏满 | 脏满 | 脏满 | 空 |
### 代码流程
#### 初始化流程
初始化主要确定：可写入区块、空区块数量以及可写入区块内的偏移（即下一个数据写入的地方）。
#### 整理区块流程
#### 写入数据流程
#### 读取数据流程
#### 查找数据流程
